#include<cstdio>
#include<algorithm>
#include<cmath>

#define N 1000
#define RED 0
#define BLACK 1

using namespace std;

struct node{
    int key;
    bool color;
    node *left, *right, *p;
};

struct tree{
    node *root, *nil;
};

void inorder_rb_walk(tree *t, node *x){
    if (x != t->nil) {
        inorder_rb_walk(t, x->left);
        printf("%d ", x->key);
        inorder_rb_walk(t, x->right);
    }
}

node* rb_search(tree *t, node *x, int k){
    if (x == t->nil || k == x->key)
        return x;
    if (k < x->key)
        return rb_search(t, x->left, k);
    else
        return rb_search(t, x->right, k);
}

node* iterative_rb_search(tree *t, node *x, int k){
    while(x != t->nil && k != x->key){
        if (k < x->key)
            x = x->left;
        else
            x = x->right;
    }
    return x;
}

node* rb_minimum(tree *t, node *x){
    while(x->left != t->nil)
        x = x->left;
    return x;
}

node* rb_maximum(tree *t, node *x){
    while(x->right != t->nil)
        x = x->right;
    return x;
}

node* rb_successor(tree *t, node *x){
    if (x->right != t->nil)
        return rb_minimum(t, x->right);
    node *y = x->p;
    while(y != t->nil && x==y->right){
        x = y;
        y = y->p;
    }
    return y;
}

node* rb_predecessor(tree *t, node *x){
    if (x->left!= t->nil)
        return rb_maximum(t, x->left);
    node *y = x->p;
    while(y != t->nil && x==y->left){
        x = y;
        y = y->p;
    }
    return y;
}

void left_rotate(tree *t, node *x){
    node *y = x->right;
    x->right = y->left;
    if (y->left != t->nil)
        y->left->p = x;
    y->p = x->p;
    if (x->p == t->nil)
        t->root = y;
    else if (x == x->p->left)
        x->p->left = y;
    else
        x->p->right = y;
    y->left = x;
    x->p = y;
}

void right_rotate(tree *t, node *x){
    node *y = x->left;
    x->left = y->right;
    if (y->right!= t->nil)
        y->right->p = x;
    y->p = x->p;
    if (x->p == t->nil)
        t->root = y;
    else if (x == x->p->left)
        x->p->left = y;
    else
        x->p->right = y;
    y->right= x;
    x->p = y; 
}

void rb_insert_fixup(tree *t, node *z){
    while (z->p->color == RED){
        if (z->p == z->p->p->left){
            node *y = z->p->p->right;
            if (y->color == RED){
                z->p->color = BLACK;
                y->color = BLACK;
                z->p->p->color = RED;
                z = z->p->p;
            } else{
                if (z == z->p->right) {
                    z = z->p;
                    left_rotate(t, z);
                }
                z->p->color = BLACK;
                z->p->p->color = RED;
                right_rotate(t, z->p->p);
            }
        } else {
            node *y = z->p->p->left;
            if (y->color == RED){
                z->p->color = BLACK;
                y->color = BLACK;
                z->p->p->color = RED;
                z = z->p->p;
            } else{
                if (z == z->p->left) {
                    z = z->p;
                    right_rotate(t, z);
                }
                z->p->color = BLACK;
                z->p->p->color = RED;
                left_rotate(t, z->p->p);
            }
        }
    }
    t->root->color = BLACK;
}

void rb_insert(tree *t, node *z){
    node *y = t->nil;
    node *x = t->root;
    while (x != t->nil){
        y = x;
        if (z->key < x->key)
            x = x->left;
        else
            x = x->right;
    }
    z->p = y;
    if (y == t->nil)
        t->root = z;
    else if (z->key < y->key)
        y->left = z;
    else 
        y->right = z;
    z->left = t->nil;
    z->right = t->nil;
    z->color = RED;
    rb_insert_fixup(t, z);
}

void rb_transplant(tree *t, node *u, node *v){
    if (u->p == t->nil)
        t->root = v;
    else if (u == u->p->left)
        u->p->left = v;
    else
        u->p->right = v;
    v->p = u->p;
}

void rb_delete_fixup(tree *t, node *x){
    node *w;
    while (x != t->root && x->color == BLACK){
        if (x == x->p->left){
            w = x->p->right;
            if (w->color == RED){
                w->color = BLACK;
                x->p->color = RED;
                left_rotate(t, x->p);
                w = x->p->right;
            }
            if (w->left->color == BLACK && w->right->color == BLACK){
                w->color = RED;
                x = x->p;
            } else {
                if (w->right->color == BLACK){
                    w->left->color = BLACK;
                    w->color = RED;
                    right_rotate(t, w);
                    w = x->p->right;
                }
                w->color = x->p->color;
                x->p->color = BLACK;
                w->right->color = BLACK;
                left_rotate(t, x->p);
                x = t->root;
            }
        } else {
            w = x->p->left;
            if (w->color == RED){
                w->color = BLACK;
                x->p->color = RED;
                right_rotate(t, x->p);
                w = x->p->left;
            }
            if (w->left->color == BLACK && w->right->color == BLACK){
                w->color = RED;
                x = x->p;
            } else {
                if (w->left->color == BLACK){
                    w->right->color = BLACK;
                    w->color = RED;
                    left_rotate(t, w);
                    w = x->p->left;
                }
                w->color = x->p->color;
                x->p->color = BLACK;
                w->left->color = BLACK;
                right_rotate(t, x->p);
                x = t->root;
            }
        }
    }
    x->color = BLACK;
}

void rb_delete(tree *t, node *z){
    node *y = z;
    node *x;
    bool y_original_color = y->color;
    if (z->left == t->nil) {
        x = z->right;
        rb_transplant(t, z, z->right);
    } else if (z->right == t->nil) {
        x = z->left;
        rb_transplant(t, z, z->left);
    } else {
        y = rb_minimum(t, z->right);
        y_original_color = y->color;
        x = y->right;
        if (y->p == z){
            //
            if (x->p != y && x != t->nil){
                printf("exception!!!!!!!!!!!!!!!!!!!!!!!!!!!!!");
            }
            x->p = y;
        } else {
            rb_transplant(t, y, y->right);
            y->right = z->right;
            y->right->p = y;
        }
        rb_transplant(t, z, y);
        y->left = z->left;
        y->left->p = y;
        y->color = z->color;
    }
    if (y_original_color == BLACK)
        rb_delete_fixup(t, x);
}

tree t;
int size;
node nodes[N];
int main(){
    size = 0;
    node u;
    u.key = 0;
    u.p = u.left = u.right = NULL;
    u.color = BLACK;
    nodes[size++] = u;
    t.nil = &nodes[0];
    t.nil->p = t.nil->left = t.nil->right = t.nil;
    t.root = t.nil;
    for(int i = 0; i < 10; i++){
        int j = rand() % 100;
        u.key = j;
        nodes[size++] = u;
        printf("*** Insert %d\n", u.key);
        rb_insert(&t, &nodes[size-1]);
    }
    for(int i = 0; i < 6; i++){
        printf("%d: ", i+1);
        inorder_rb_walk(&t, t.root);
        printf("\n");
        switch(i){
            case 0:{
                node *v = rb_minimum(&t, t.root);
                if (v == t.nil)
                    printf("*** Null minimum\n");
                else
                    printf("*** Find minimum: %d\n", v->key);
                break;
                   }
            case 1:{
                int j = rand() % (size-1) +1;
                printf("*** Delete %d\n", nodes[j].key);
                rb_delete(&t, &nodes[j]);
                nodes[j] = nodes[size-1];
                size--;
                break;
                   }
            case 2:{
                int j = rand() % (size-1)+1;
                node *v = rb_successor(&t, &nodes[j]);
                printf("*** Successor %d : ", nodes[j].key);
                if (v == t.nil)
                    printf("NULL\n");
                else 
                    printf("%d\n", v->key); 
                break;
                   }
            case 3:{
                node *v = rb_maximum(&t, t.root);
                if (v == t.nil)
                    printf("*** Null maximum\n");
                else
                    printf("*** Find maximum: %d\n", v->key);
                break;
                   }
            case 4: {
                int j = rand() % (size-1)+1;
                node *v = rb_predecessor(&t, &nodes[j]);
                printf("*** Predecessor %d : ", nodes[j].key);
                if (v == t.nil)
                    printf("NULL\n");
                else
                    printf("%d\n", v->key);
                break;
                    }
        }
    }
    return 0;
}
